package com.gump.mall.demo.algorithm;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

/**
 * @auther zzc
 * @date 2020/9/9 11:20
 * 概要：算法 数据结构demo
 */
public class Demo {

    public static void main(String[] args) {

        //getMaxCountNumOne();
        //getMaxCountNumTwo();
        //System.out.println(checkByStack());
        todoByQueue(10, 5);
    }

    //约瑟夫环问题
    /*
    已知 n 个人（以编号 1，2，3...n 分别表示）围坐在一张圆桌周围。
    从编号为 k 的人开始报数，数到 m 的那个人出列；
    他的下一个人又从 1 开始报数，数到 m 的那个人又出列；
    依此规律重复下去，直到圆桌周围的人全部出列。
    这个问题的输入变量就是 n 和 m，即 n 个人和数到 m 的出列的人。
    输出的结果，就是 n 个人出列的顺序。
     */
    private static void todoByQueue(int n, int m) {
        LinkedList<Integer> q = new LinkedList<Integer>();
        for (int i = 1; i <= n; i++) {
            q.add(i);
        }
        int k = 2;
        int element = 0;
        int i = 0;
        for (; i < k; i++) {
            element = q.poll();
            q.add(element);
        }
        i = 1;
        while (q.size() > 0) {
            element = q.poll();
            if (i < m) {
                q.add(element);
                i++;
            } else {
                i = 1;
                System.out.println(element);
            }
        }

    }

    //给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
    private static String checkByStack() {
        String s = "{[()()]}";
        Stack stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (isLeft(c)) {
                stack.push(c);

            } else {
                if (stack.isEmpty()) {
                    return "非法";
                }
                char p = (char) stack.pop();
                if (!isPair(p, c)) {
                    return "非法";
                }
            }

        }
        if (stack.isEmpty()) {
            return "合法";
        }
        return null;

    }

    private static boolean isPair(char c, char p) {
        if (c == '{' && p == '}' || c == '[' && p == ']' || c == '(' && p == ')') {
            return true;
        } else {
            return false;
        }
    }

    private static boolean isLeft(char c) {
        if (c == '{' || c == '[' || c == '(') {
            return true;
        } else {
            return false;
        }
    }

    //O(n)
    private static void getMaxCountNumTwo() {
        int arr[] = {1, 3, 4, 3, 4, 1, 3};
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }
        int max_num = -1;
        int times_max = 0;
        for (Integer key : map.keySet()) {
            if (map.get(key) > times_max) {
                times_max = map.get(key);
                max_num = key;
            }
        }
        System.out.println("出现次数最多的数为:" + max_num);
    }

    //O(n2)
    private static void getMaxCountNumOne() {
        //定义了一个数组 a = [1, 3, 4, 3, 4, 1, 3]，并会在这个数组中查找出现次数最多的那个数字
        int arr[] = {1, 3, 4, 3, 4, 1, 3};
        int max_num = -1;
        int times_max = 0;
        int times_tmp = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    times_tmp += 1;
                }
            }
            if (times_tmp > times_max) {
                times_max = times_tmp;
                max_num = arr[i];
            }
        }
        System.out.println("出现次数最多的数为:" + max_num);
    }
}
